package JZOffer;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 剑指 Offer 41. 数据流中的中位数
 * 如何得到一个数据流中的中位数？
 * 如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * */
//1.放入数组中排序 o（n log n）
//2.二分法  寻找地方插入 o（n）
// 3.两个堆来维护   o(log n)

class MedianFinder {
    Queue<Integer> max;
    Queue<Integer> min;

    /** initialize your data structure here. */
    public MedianFinder() {
        max = new PriorityQueue<>();
        min = new PriorityQueue<>((o1, o2)->(o2.compareTo(o1)));
    }

    public void addNum(int num) {
        max.add(num);
        min.add(max.poll());
        if (max.size() < min.size()) {
            max.add(min.poll());
        }
    }

    public double findMedian() {
        if (max.size() > min.size()) return max.peek();
        return (max.peek() + min.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */